package srcInterviewPrep;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;

public final class IntervalAssignment
{
    public static HashMap<Integer, List<Interval>> AssignProcessors(Interval[] intervals)
    {
        // null check for intervals
        // intervals is expected to be sorted by id
        
        List<Point> allPoints = GetAllPoints(intervals);
        
        Collections.sort(allPoints);
        
        LinkedHashSet<Integer> availableProcs = new LinkedHashSet<Integer>();
        HashMap<Integer, Integer> runningIntervalMap = new HashMap<Integer, Integer>();
        HashMap<Integer, List<Interval>> intervalAssignmentMap = new HashMap<Integer, List<Interval>>();
        
        int numProcs = 0;
        
        for (Point p : allPoints)
        {
            if (p.Type == PointType.Start)
            {
                if (availableProcs.isEmpty())
                {
                    ++numProcs;
                    intervalAssignmentMap.put(numProcs, new ArrayList<Interval>());
                    intervalAssignmentMap.get(numProcs).add(intervals[p.Id]);
                    runningIntervalMap.put(p.Id, numProcs);
                }
                else
                {
                    int proc = availableProcs.iterator().next();
                    availableProcs.remove(proc);
                    runningIntervalMap.put(p.Id, proc);
                    intervalAssignmentMap.get(proc).add(intervals[p.Id]);
                }
            }
            else
            {
                int proc = runningIntervalMap.get(p.Id);
                runningIntervalMap.remove(p.Id);
                availableProcs.add(proc);
            }
        }
        
        return intervalAssignmentMap;
    }
    
    private static List<Point> GetAllPoints(Interval[] intervals)
    {
        List<Point> points = new ArrayList<Point>();
        
        for (Interval i : intervals)
        {
            Point p1 = new Point(i.Id, i.StartTime, PointType.Start);
            Point p2 = new Point(i.Id, i.FinishTime, PointType.Finish);
            points.add(p1);
            points.add(p2);
        }
        
        return points;
    }
}
